By “material body” is meant any material substance or object exhibiting an individuality and able to be detected and identified by an appropriate sensor. Thus, inanimate objects, be they natural or artificial, plants, animals, human beings are considered to be material bodies, as are also liquid or solid particles in suspension in the air, such as clouds, or indeed liquid or gaseous masses.
The invention can also be used in the image reconstruction field, in order to determine the information to be used to reconstruct an image in a given direction of vision, for example along a sensor's axis of observation or vision.
In the object perception sector, two main families of perception technique exist: geometric schemes, which are aimed at identifying the geometry of the objects of the surrounding space, and occupancy grid based schemes, which are aimed at determining whether a certain site is occupied by an obstacle, more generally by a material body. The invention pertains to occupancy grid based techniques.
To capture and interpret the environment, the perception system employs distance sensors which advise as regards the remoteness of the obstacles in the vicinity. These distance sensors can conventionally be: radars, ultrasound sensors, 3D imagers, stereovision systems, LIDARs (Light Detection And Ranging), etc. To improve the robustness of the perception function and to increase the overall field of vision, the system incorporates several heterogeneous sensors. One of the difficulties is to determine, precisely and in a reasonable computation time, the cells liable to be traversed or observed by a moving device so as to associate with them an item of information relating to the presence or to the absence of an obstacle. The constraints encountered are mainly of two kinds, computational need and memory need.
An occupancy grid is a partition of the observed space into cells. For each cell, its state is sought. For example, two issues may be possible, “occupied” or “empty. The certainty level regarding the occupancy of a cell is then given, for example, with the probability of the event “O=occupied” denoted P(O) and with the complementary P(e)=1−P(O). In other applications, a value or a parameter encoding the knowledge of another spatial magnitude, such as the air pollution, or the temperature of a zone, may be associated with a cell. The probabilities of occupancy are, for example, estimated on the basis of the knowledge, provided by the sensors, of the exterior environment.
The example given in FIG. 1 represents the implementation of the framework of the occupancy grids for a vehicle 1 equipped with a distance sensor 2 with the aid of a regular grid G. Each cell of this grid represents a fragment of the space situated in front of the vehicle, and for each cell the probability of occupancy is computed. A value of greater than 0.5 indicates a higher certainty that the cell in question is occupied. Conversely, a value of less than 0.5 indicates that the cell has more chance of being free. The probability equal to 0.5 indicates that no relevant information is available to pronounce upon the state of the cell.
As a function of the applications, it may be critical to determine the occupied cells (obstacle trajectory analysis, target following, etc.) or the empty cells (displacement planning, avoidance, etc.). The advantage of the framework of the occupancy grids is that with a single modeling of the environment that is rather simple, both types of information are represented.
In FIG. 2, a 1D sensor model is used for the evaluation of the occupancy of a cell. This sensor model known to the person skilled in the art allows the evaluation of the occupancy in a 1D grid represented on the left of FIG. 2. The 1D occupancy information is thereafter mapped into a 2D model, right part of FIG. 2. This requires firstly positioning the sensor S in the grid, and then the target F, and determining all the cells traversed by the half-line [SF] in the grid. When several sensors are used, for each of the cells the information is then merged with that of the other sensors having relevant information for the cell in question. In 1D or in 2D, the cells whose occupancy information (probability of occupancy, for example) has to be updated are situated between S and F and also beyond F, this being because of the uncertainty related to the sensor's measurement precision.
One of the problems in the computation of 2D or 3D occupancy grids, when using several heterogeneous sensors positioned at various sites of the space studied, is that the computational need explodes. Indeed, for each measurement the 1D occupancy profile corresponding to a cell is computed, and then this 1D profile is mapped and merged in a grid of larger dimension. The magnitudes manipulated are generally probabilities and distances, traditionally expressed with the aid of real numbers. Most of the time these real numbers are represented with the aid of floating-point numbers which require the digital system to be capable of supporting floating-point arithmetical operations. Moreover, and independently of any digital representation, the mapping problem is intrinsically tricky since it implements computation utilizing information at various spatial resolutions. Indeed, the position of the sensors and their responses are, most of the time, known to spatial resolutions greater than that of the grid. The representation of the distances with the aid of floating-point numbers is then often used, since it makes it possible to dispense in the computation with considerations regarding the precision of the spatial information.
Various schemes are known from the prior art for determining occupied cells in grids and also for the way of obtaining the information advising a cell.
The document entitled “A Fast Voxel Traversal Algorithm for Ray Tracing” by A. W. John Amanatides, Eurographics, 1987, discloses a line tracing algorithm in a 2D or 3D environment. This algorithm consists in traveling over the 2D or 3D parametric straight line equation and in collecting the set of cells traversed. This algorithm nonetheless requires a floating-point operation at each iteration (switch to the next cell).
The document by A. Hornung, K. M. Wurm, M. Bennewitz, C. Stachniss, and W. Burgard entitled “OctoMap: an efficient probabilistic 3D mapping framework based on octrees” published in Autonomous Robots, 2013, describes a scheme for representing three-dimensional occupancy grids. The general framework allows the continuous incorporation of information of sensors and describes how the sensory information is mapped in the environment. The scheme then utilizes the aforementioned work by Amanatides to map the environment information.
The algorithm described in the document by J. E. Bresenham entitled “Algorithm for computer control of a digital plotter”, IBM Systems Journal, 1965, makes it possible to plot a line on a screen. The objective of the algorithm is to be ultra-efficacious, and to give a result which is satisfying to the eye. From a mathematical point of view, the principle consists in determining all the pixels (˜cells) traversed by a line (˜sensor measurement). This algorithm requires only integer operations with neither multiplication nor division. On the other hand, certain pixels traversed by the line will not be displayed, and certain displayed pixels are not mathematically traversed by the line.
The applicant's patent application FR1558919 describes a scheme making it possible to carry out the fusion of the occupancy information at the level of a cell. This technique makes it possible to construct the result of the fusion by means of arithmetical operations alone. On the other hand, the scheme does not describe how to solve the problem of the mapping of the 2D or 3D information in integer arithmetic.
In patent application WO2013189482, a representation of the occupancy grids with the aid of quadtree is proposed. The use of quadtrees for 2D occupancy grids for automotive applications is motivated for two reasons mainly:                The sensors do not necessarily work at the same resolutions, and it may be judicious to have a hierarchical data structure which allows multi-resolution information processing,        The applications do not necessarily utilize information at the same resolution (emergency braking, vs navigation for example).        
The technical difficulty solved by this scheme makes it possible to construct an item of information of lower resolution from an item of information of smaller resolution. It does not describe how the mapping of the information is carried out, at whatever resolution it be.
It is therefore important to have available a scheme making it possible to determine, simply and with a small number of computational resources, the coordinates of the cells whose occupancy probability value, or a value representative of the content of the cell traversed, it is desired to update.
In the subsequent description, the expression “cell traversed” designates a cell which is traversed or observed by the field of vision of a sensor or of an observer.
An error function Err( ) is defined as a function which makes it possible to compute an error value representative of the position of at least one coordinate of a point belonging to an occupancy grid with respect to a path defined in an observation space. Examples will be given hereinafter.